Міністерство освіти і науки України
Національний університет ’Львівська політехніка’
Кафедра ЕОМ
Курсова робота
Із дисципліни”Структури даних та алгоритми”
з курсу ”Основи інформатики, алгоритмізації та мов програмування ”
Львів 2004
ЗМІСТ
ВСТУП 2
1. ВИМОГИ ДО ПОРЯДКУ ВИКОНАННЯ ТА ОФОРМЛЕННЯ
КУРСОВОЇ РОБОТИ 3
1.1. Вимоги до розробки програмних продуктів 4
1.2. Вимоги до оформлення пояснювальної записки 4
2. ВАРІАНТИ ЗАВДАНЬ 6
2.1. Завдання 1 6
2.2. Завдання 2 8
2.2.1. Завдання 2.1 9
2.2.2. Завдання 2.2 9
2.3. Завдання 3 10
3. ДОДАТОК 9
3.1. Додаток 1 11
3.2. Додаток 2.1 18
3.3. Додаток 2.2 20
3.4. Додаток 3 22
4. СПИСОК ЛІТЕРАТУРИ 30
ВСТУП
Комп’ютер – це машина, що обробляє інформацію. Вивчення засобів програмування передбачає вивчення того, яким чином ця інформація організована всередині ЕОМ, як вона обробляється і як може бути використана. Тому, для вивчення дисципліни студенту особливо важливо зрозуміти концепцію організації даних і роботи з ними.
Програма представляє собою в кінцевому рахунку конкретні формулювання абстрактних алгоритмів, що базуються на конкретних представленнях і структурах даних. Зрозуміло, що рішення про структури даних які необхідно застосувати неможливо прийняти без знання алгоритмів, що застусовуються до цих даних, і навпаки, вибір алгоритмів суттєво залежить від вибраних структур даних. Отже, структури програм і структури даних нерозривно пов’язані.
В курсовій роботі спочатку розглядаються фундаментальні структури які складаються з простих даних. Вони представляють собою компоненти, з яких складаються більш складні структури. Змінні фундаментальної структури можуть змінювати тільки своє значення, зберігаючи незмінною свою форму. Таким чином, розмір пам’яті яку вони займають залишається постійним. Навпаки, ускладнені структури характеризуються зміною не тільки значення, але й форми під час виконання програми. Тому для йх реалізації необхідно застусовувати більш складні прийоми. Послідовний файл займає проміжне значення, поскільки хоча його довжина й змінюється, але ця зміна форми є тривіальною. Поскільки послідовний файл грає важливу роль практично у всіх обчислювальних системах, він буде розглядатись разом з фундаментальними структурами.
В першому завданні курсової роботи досліджується представлення в пам’яті комп’ютера даних статичної структури. Розглядаються прості (цілі, дійсні, символьні, логічні, перелічувані, обмежені) і складові або фундаментальні (масиви, множини, записи, рядки символів, файли) структури даних.
В другому завданні будується одна з більш складних динамічних структур даних (стеки, черги, списки, дерева, графи), розробляються алгоритми і програмні реалізації роботи з нею і за їх допомогою розв’язується прикладна задача.
В другому завданні будується один з методів сортування або пошуку. Досліджуються основні характеристики цього метода і проводиться порівняння ефективностей даного метода і класичних методів. Алгоритмам сортування і пошуку приділяється ...